package com.bins.knowledge.point.algorithm;

import java.util.*;

/**
 * 给定一个链表，判断它是否含有环。如果链表中有环，则返回 true；否则返回 false。
 */
public class LinkedListAsGraph {

    // 链表节点定义
    static class ListNode {
        int value;
        ListNode next;
        ListNode(int x) { value = x; }
    }

    public static void main(String[] args) {
        // 创建有环链表
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 4 → 2 (形成环)
        node5.next = node2; // 5 → 2

        // 用图表示（邻接表）
        Map<ListNode, ListNode> graph = new HashMap<>();
        graph.put(node1, node2);
        graph.put(node2, node3);
        graph.put(node3, node4);
        graph.put(node4, node2); // 环
        graph.put(node5, node2);

        // 打印图
        System.out.println("图表示（邻接表）：");
        for (Map.Entry<ListNode, ListNode> entry : graph.entrySet()) {
            System.out.println(entry.getKey().value + " → " + entry.getValue().value);
        }
    }
}